The channel used in telecommunications systems often causes interference to data transmission Interference occurs in all kinds of systems, but especially in wireless telecommunications systems, the transmission path attenuates and distorts in many different ways the signal being transmitted. The multipath propagation of the signal, different fades and reflections, and other signals being transmitted on the same transmission path typically cause interference on the transmission path.
To reduce the impact of the interference, several coding methods have been developed to protect signals from interference and to endeavour to eliminate errors caused by interference in signals. Convolutional coding is a much-used coding method. In convolutional coding, the signal to be transmitted that is made up of symbols is coded into code words that are based on the convolution of the symbols to be transmitted either with themselves or with another signal. The coding ratio and generator polynomials define the convolutional code. The coding ratio (kin) refers to the number (n) of the produced coded symbols in relation to the number (k) of the symbols to be coded. The coder is often a shift register. The constraint length (K) of a code often refers to the length of the shift register. The coder can be considered a state machine having 2K-1 states.
A receiver decodes the coded signal that propagated through the channel. A convolutional code is usually decoded using a trellis whose nodes describe the states of the encoder used in coding the signal, and the paths between the nodes belonging to different stages of the trellis describe the allowed state transitions. A decoder tries to find out the consecutive states of the coder, i.e. the transitions from one state to another. To find out the transitions, the decoder calculates metrics, of which there are two types: path metrics (or state metrics) and branch metrics. Path metrics represent the probability of the set of symbols in the received signal leading to the state described by the node in question. Branch metrics represent the probabilities of different transitions.
A convolutional code is usually decoded by means of the Viterbi algorithm. The Viterbi algorithm is a computationally demanding task. A general problem with the Viterbi algorithm is that when the constraint length is long (e.g. 9, as in WCDMA of the UMTS system), the Viterbi algorithm must search through 2(9-1), i.e. 256, states to decode one bit. Efficient signal processing algorithms are still being searched for wireless telecommunications systems in particular, in which the aim is to minimize the size and power consumption of subscriber terminals. A computationally efficient algorithm for speech or data decoding is the M algorithm that is a search algorithm simplified from the Viterbi algorithm. Using the M algorithm makes it possible to reduce the number of searched states, because only M best paths are selected for continuation in the trellis stages instead of all paths. When a suitable value is selected for M, the performance of the decoder does not, however, become significantly poorer. For instance, in the above-mentioned system, M can obtain the value 128, i.e. half of the possible paths are selected for continuation at each stage.
One problem with the use of the M algorithm is the selection of paths for continuation amongst all paths. Typically, the sorting of n elements requires n2/2 comparison operations, and this is a computationally demanding task. Let us assume that the decoding of one bit by DSP (digital signal processing) in WCDMA requires approximately 500 clock cycles when a full search algorithm is used. If the M algorithm is used, the number of states to be searched is smaller but correspondingly, sorting increases the complexity. When sorting 16 elements, 128 comparison operations are required. Thus using the M algorithm with the best 16 paths leads to almost the same complexity as a full search algorithm. If a 256-state code is used, a full sort requires n2/2, i.e. 32768 comparisons. A full search is too complex an operation to implement by the traditional methods.
One known solution for implementing the M algorithm is disclosed in publication S. J. Simmons: A Nonsorting VLSI structure for implementing the (M,L) algorithm, IEEE Journal on Selected Areas in Communications, Vol. 6, No. 3, April 1988, pages 538 to 546. The disclosed solution does not perform the actual sorting, but examines several different path metrics at the same time, starting from the most significant bit. While the different paths are examined, decisions are made on keeping or rejecting the routes. If the examined route is opposite to an already selected route, it is rejected. However, the solution disclosed in the publication works poorly in situations where the trellis is large, as in WCDMA of the UMTS system, for instance.
The trellis structure is used not only in the decoding of convolutional codes, but also in several other applications, such as channel equalization. The same above-mentioned problems also apply to these solutions, when the size of the trellis increases.
Thus, to minimize the size and power consumption of devices, more efficient methods than before are needed for searching through a trellis, methods that are fast and whose implementation as ASIC structures does not require much space.